package week_05;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 1665. 完成所有任务的最少初始能量
 * 给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：
 * <p>
 * actuali 是完成第 i 个任务 需要耗费 的实际能量。
 * minimumi 是开始第 i 个任务前需要达到的最低能量。
 * 比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。
 * <p>
 * 你可以按照 任意顺序 完成任务。
 * <p>
 * 请你返回完成所有任务的 最少 初始能量。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：tasks = [[1,2],[2,4],[4,8]]
 * 输出：8
 * 解释：
 * 一开始有 8 能量，我们按照如下顺序完成任务：
 * - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
 * - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
 * - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
 * 注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。
 * 示例 2：
 * <p>
 * 输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
 * 输出：32
 * 解释：
 * 一开始有 32 能量，我们按照如下顺序完成任务：
 * - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
 * - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
 * - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
 * - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
 * - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。
 * 示例 3：
 * <p>
 * 输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
 * 输出：27
 * 解释：
 * 一开始有 27 能量，我们按照如下顺序完成任务：
 * - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
 * - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
 * - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
 * - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
 * - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
 * - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。
 */

public class MinimumEffort_1665 {
    public int minimumEffort(int[][] tasks) {
        List<int[]> taskList = new ArrayList<>();
        for (int[] item : tasks) {
            taskList.add(item);
        }
        List<Character> list;
        Collections.sort(taskList, (o1, o2) -> (o1[0] - o1[1] - o2[0] + o2[1]));
        int engry = 0;
        for (int i = tasks.length - 1; i > 0; i++) {
            int[] task = taskList.get(i);
            engry = Math.max(task[0] + engry, task[1]);
        }
        return engry;

    }
}
/**
 * 先做 p ，再做 p，那么就如图示的顺序 i -> i+1
 * 定义做 p 之前至少需要的初始能量为 min[p]，做完p任务实际消耗 a[p]
 * 定义做 q 之前至少需要的初始能量为 min[q]，做完q任务实际消耗 a[q]
 * 完成 i+2 ... n 的部分需要的能量设为 S，即达到 i+2 时，至少还有 S 的能量
 * <p>
 * 那么，先做 p 所需的初始能量 max（min[p]，i 到 n 之间的能量条）
 * 如果 min[p] 小于后者，那肯定完不成 p -> q，所以是取较大的能量数 ;
 * <p>
 * i 到 n 之间的能量条 ： a [p]  + max （min[q] ，a[q] + S）
 * 第二项同理，如果 min[q] 小于后者，也完不成 q -> i+2；
 * <p>
 * 也就有第一个式子：
 * max（min[p]， a [p]  + max （min[q] ，a[q] + S））
 **/